CoCalc Logo Icon
DocsShareSupport News Sign UpSign In
Views: 94
Image: ubuntu2004
Embed | Download | Raw |
Kernel: hardproblems
import random from IPython.core.display import SVG import pyomo.environ as pyo from pysat.solvers import Solver from pysat.formula import CNF import py_svg_combinatorics as psc from ipywidgets import widgets, HBox from collections import Counter from pprint import pprint from random import randint import numpy as np from IPython.display import IFrame import IPython from copy import copy import os from pathlib import Path nbname = '' try: nbname = __vsc_ipynb_file__ except: if 'COCALC_JUPYTER_FILENAME' in os.environ: nbname = os.environ['COCALC_JUPYTER_FILENAME'] title_ = Path(nbname).stem.replace('-', '_').title() IFrame(f'https://discopal.ispras.ru/index.php?title=Hardprob/{title_}&useskin=cleanmonobook', width=1280, height=300)

Постановка задачи

Представим, что мы имеем базовый блок размера basic_block_size, который представляет собой последовательность инструкций.

Каждая инструкция использует до instruction_uses_max виртуальных регистров и может быть определением нового виртуального регистра (а может и нет).

Задача регистровой аллокации задаётся вопросом, есть ли отображение v_reg -> phys_reg, такое что для любой инструкции образ её используемых регистров не будет содержать одинаковых физических регистров (также мы предполагаем, что после использования регистра он сразу же сохраняется в памяти, а перед использованием из неё достаётся, что позволяет нам присваивать одинаковые физические регистры тем виртуальным регистрам, live ranges которых пересекаются. В настоящем аллокаторе, конечно же, для поиска оптимальных spill/restore промежутков используется отдельная эвристика жадного "разрезания", старающая минимизировать количество операций с памятью).

Оптимизационная версия задачи "минимальная локальная регистровая аллокация", задаёт вопрос об аллокации минимальной стоимости, то есть минимизируем сумму использования регистра N на стоимость использования S_N по всем операндам всех инструкций.

phys_regs_amount = 4 phys_regs_costs = np.arange(1, phys_regs_amount + 1) basic_block_size = 16 instruction_uses_max = int(phys_regs_amount / 2) virtual_alives = [0, 1] virtual_uses = [] for _ in range(basic_block_size): # Каждая инструкция использует до instruction_uses_max виртуальных регистров virtual_uses.append([f"{i:02}" for i in np.random.choice(virtual_alives, instruction_uses_max)]) # Инструкция с шансом 0.5 может определить новый виртуальный регистр if np.random.choice([True, False]): virtual_alives.append(virtual_alives[-1] + 1)

Для визуализации будем считать, что каждая строка представляет инструкцию, а каждый стобец представляет использование i-го виртуального регистра.

svg = psc.subsets2svg(virtual_uses) SVG(data=svg)
Image in a Jupyter notebook
def get_model(instruction_uses, phys_regs_costs, virtual_regs_amount): model = pyo.ConcreteModel() # Множество физических регистров model.phys_regs = pyo.Set(initialize=range(len(phys_regs_costs))) # Сопоставление каждому физическому регистру его стоимости model.phys_costs = pyo.Param(model.phys_regs, initialize=phys_regs_costs) # Множество виртуальных регистров model.virt_regs = pyo.Set(initialize=range(virtual_regs_amount)) # Хотим составить отображение из виртуальных регистров на физические model.alloca = pyo.Var(model.virt_regs, model.phys_regs, domain=pyo.Binary) # Составляем множества плохих пар виртуальных регистров (встречаемых в используемых для одинаковых инструкций) model.bad_pairs = pyo.Set(initialize=sorted(set([(int(i), int(j)) for uses in instruction_uses for i in uses for j in uses if i < j]))) # ЦЕЛЬ: минимизировать стоимость использования физических регистров после аллокации model.obj = pyo.Objective(expr=sum(model.phys_costs[p] * model.alloca[v, p] for v in model.virt_regs for p in model.phys_regs)) # ОГРАНИЧЕНИЕ: каждому виртуальному регистру сопоставляем ровно 1 физический @model.Constraint(model.virt_regs) def виртуальному_один_физический(m, v): return sum(model.alloca[v, phys] for phys in m.phys_regs) == 1 # ОГРАНИЧЕНИЕ: каждый физический регистр должен использоваться каждой инструкцией не более одного раза @model.Constraint(model.bad_pairs, model.phys_regs) def использование_одного_физического(m, first, second, reg): return (m.alloca[first, reg] + m.alloca[second, reg]) <= 1 return model
m = get_model(virtual_uses, phys_regs_costs, len(virtual_alives)) m.pprint()
5 Set Declarations alloca_index : Size=1, Index=None, Ordered=True Key : Dimen : Domain : Size : Members None : 2 : virt_regs*phys_regs : 40 : {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3), (6, 0), (6, 1), (6, 2), (6, 3), (7, 0), (7, 1), (7, 2), (7, 3), (8, 0), (8, 1), (8, 2), (8, 3), (9, 0), (9, 1), (9, 2), (9, 3)} bad_pairs : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 2 : Any : 13 : {(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 8), (2, 9), (3, 4), (3, 5), (4, 5), (7, 8)} phys_regs : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 4 : {0, 1, 2, 3} virt_regs : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} использование_одного_физического_index : Size=1, Index=None, Ordered=True Key : Dimen : Domain : Size : Members None : 3 : bad_pairs*phys_regs : 52 : {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 3, 0), (0, 3, 1), (0, 3, 2), (0, 3, 3), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 0), (1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 4, 0), (1, 4, 1), (1, 4, 2), (1, 4, 3), (1, 5, 0), (1, 5, 1), (1, 5, 2), (1, 5, 3), (1, 6, 0), (1, 6, 1), (1, 6, 2), (1, 6, 3), (2, 8, 0), (2, 8, 1), (2, 8, 2), (2, 8, 3), (2, 9, 0), (2, 9, 1), (2, 9, 2), (2, 9, 3), (3, 4, 0), (3, 4, 1), (3, 4, 2), (3, 4, 3), (3, 5, 0), (3, 5, 1), (3, 5, 2), (3, 5, 3), (4, 5, 0), (4, 5, 1), (4, 5, 2), (4, 5, 3), (7, 8, 0), (7, 8, 1), (7, 8, 2), (7, 8, 3)} 1 Param Declarations phys_costs : Size=4, Index=phys_regs, Domain=Any, Default=None, Mutable=False Key : Value 0 : 1 1 : 2 2 : 3 3 : 4 1 Var Declarations alloca : Size=40, Index=alloca_index Key : Lower : Value : Upper : Fixed : Stale : Domain (0, 0) : 0 : None : 1 : False : True : Binary (0, 1) : 0 : None : 1 : False : True : Binary (0, 2) : 0 : None : 1 : False : True : Binary (0, 3) : 0 : None : 1 : False : True : Binary (1, 0) : 0 : None : 1 : False : True : Binary (1, 1) : 0 : None : 1 : False : True : Binary (1, 2) : 0 : None : 1 : False : True : Binary (1, 3) : 0 : None : 1 : False : True : Binary (2, 0) : 0 : None : 1 : False : True : Binary (2, 1) : 0 : None : 1 : False : True : Binary (2, 2) : 0 : None : 1 : False : True : Binary (2, 3) : 0 : None : 1 : False : True : Binary (3, 0) : 0 : None : 1 : False : True : Binary (3, 1) : 0 : None : 1 : False : True : Binary (3, 2) : 0 : None : 1 : False : True : Binary (3, 3) : 0 : None : 1 : False : True : Binary (4, 0) : 0 : None : 1 : False : True : Binary (4, 1) : 0 : None : 1 : False : True : Binary (4, 2) : 0 : None : 1 : False : True : Binary (4, 3) : 0 : None : 1 : False : True : Binary (5, 0) : 0 : None : 1 : False : True : Binary (5, 1) : 0 : None : 1 : False : True : Binary (5, 2) : 0 : None : 1 : False : True : Binary (5, 3) : 0 : None : 1 : False : True : Binary (6, 0) : 0 : None : 1 : False : True : Binary (6, 1) : 0 : None : 1 : False : True : Binary (6, 2) : 0 : None : 1 : False : True : Binary (6, 3) : 0 : None : 1 : False : True : Binary (7, 0) : 0 : None : 1 : False : True : Binary (7, 1) : 0 : None : 1 : False : True : Binary (7, 2) : 0 : None : 1 : False : True : Binary (7, 3) : 0 : None : 1 : False : True : Binary (8, 0) : 0 : None : 1 : False : True : Binary (8, 1) : 0 : None : 1 : False : True : Binary (8, 2) : 0 : None : 1 : False : True : Binary (8, 3) : 0 : None : 1 : False : True : Binary (9, 0) : 0 : None : 1 : False : True : Binary (9, 1) : 0 : None : 1 : False : True : Binary (9, 2) : 0 : None : 1 : False : True : Binary (9, 3) : 0 : None : 1 : False : True : Binary 1 Objective Declarations obj : Size=1, Index=None, Active=True Key : Active : Sense : Expression None : True : minimize : alloca[0,0] + 2*alloca[0,1] + 3*alloca[0,2] + 4*alloca[0,3] + alloca[1,0] + 2*alloca[1,1] + 3*alloca[1,2] + 4*alloca[1,3] + alloca[2,0] + 2*alloca[2,1] + 3*alloca[2,2] + 4*alloca[2,3] + alloca[3,0] + 2*alloca[3,1] + 3*alloca[3,2] + 4*alloca[3,3] + alloca[4,0] + 2*alloca[4,1] + 3*alloca[4,2] + 4*alloca[4,3] + alloca[5,0] + 2*alloca[5,1] + 3*alloca[5,2] + 4*alloca[5,3] + alloca[6,0] + 2*alloca[6,1] + 3*alloca[6,2] + 4*alloca[6,3] + alloca[7,0] + 2*alloca[7,1] + 3*alloca[7,2] + 4*alloca[7,3] + alloca[8,0] + 2*alloca[8,1] + 3*alloca[8,2] + 4*alloca[8,3] + alloca[9,0] + 2*alloca[9,1] + 3*alloca[9,2] + 4*alloca[9,3] 2 Constraint Declarations виртуальному_один_физический : Size=10, Index=virt_regs, Active=True Key : Lower : Body : Upper : Active 0 : 1.0 : alloca[0,0] + alloca[0,1] + alloca[0,2] + alloca[0,3] : 1.0 : True 1 : 1.0 : alloca[1,0] + alloca[1,1] + alloca[1,2] + alloca[1,3] : 1.0 : True 2 : 1.0 : alloca[2,0] + alloca[2,1] + alloca[2,2] + alloca[2,3] : 1.0 : True 3 : 1.0 : alloca[3,0] + alloca[3,1] + alloca[3,2] + alloca[3,3] : 1.0 : True 4 : 1.0 : alloca[4,0] + alloca[4,1] + alloca[4,2] + alloca[4,3] : 1.0 : True 5 : 1.0 : alloca[5,0] + alloca[5,1] + alloca[5,2] + alloca[5,3] : 1.0 : True 6 : 1.0 : alloca[6,0] + alloca[6,1] + alloca[6,2] + alloca[6,3] : 1.0 : True 7 : 1.0 : alloca[7,0] + alloca[7,1] + alloca[7,2] + alloca[7,3] : 1.0 : True 8 : 1.0 : alloca[8,0] + alloca[8,1] + alloca[8,2] + alloca[8,3] : 1.0 : True 9 : 1.0 : alloca[9,0] + alloca[9,1] + alloca[9,2] + alloca[9,3] : 1.0 : True использование_одного_физического : Size=52, Index=использование_одного_физического_index, Active=True Key : Lower : Body : Upper : Active (0, 1, 0) : -Inf : alloca[0,0] + alloca[1,0] : 1.0 : True (0, 1, 1) : -Inf : alloca[0,1] + alloca[1,1] : 1.0 : True (0, 1, 2) : -Inf : alloca[0,2] + alloca[1,2] : 1.0 : True (0, 1, 3) : -Inf : alloca[0,3] + alloca[1,3] : 1.0 : True (0, 3, 0) : -Inf : alloca[0,0] + alloca[3,0] : 1.0 : True (0, 3, 1) : -Inf : alloca[0,1] + alloca[3,1] : 1.0 : True (0, 3, 2) : -Inf : alloca[0,2] + alloca[3,2] : 1.0 : True (0, 3, 3) : -Inf : alloca[0,3] + alloca[3,3] : 1.0 : True (1, 2, 0) : -Inf : alloca[1,0] + alloca[2,0] : 1.0 : True (1, 2, 1) : -Inf : alloca[1,1] + alloca[2,1] : 1.0 : True (1, 2, 2) : -Inf : alloca[1,2] + alloca[2,2] : 1.0 : True (1, 2, 3) : -Inf : alloca[1,3] + alloca[2,3] : 1.0 : True (1, 3, 0) : -Inf : alloca[1,0] + alloca[3,0] : 1.0 : True (1, 3, 1) : -Inf : alloca[1,1] + alloca[3,1] : 1.0 : True (1, 3, 2) : -Inf : alloca[1,2] + alloca[3,2] : 1.0 : True (1, 3, 3) : -Inf : alloca[1,3] + alloca[3,3] : 1.0 : True (1, 4, 0) : -Inf : alloca[1,0] + alloca[4,0] : 1.0 : True (1, 4, 1) : -Inf : alloca[1,1] + alloca[4,1] : 1.0 : True (1, 4, 2) : -Inf : alloca[1,2] + alloca[4,2] : 1.0 : True (1, 4, 3) : -Inf : alloca[1,3] + alloca[4,3] : 1.0 : True (1, 5, 0) : -Inf : alloca[1,0] + alloca[5,0] : 1.0 : True (1, 5, 1) : -Inf : alloca[1,1] + alloca[5,1] : 1.0 : True (1, 5, 2) : -Inf : alloca[1,2] + alloca[5,2] : 1.0 : True (1, 5, 3) : -Inf : alloca[1,3] + alloca[5,3] : 1.0 : True (1, 6, 0) : -Inf : alloca[1,0] + alloca[6,0] : 1.0 : True (1, 6, 1) : -Inf : alloca[1,1] + alloca[6,1] : 1.0 : True (1, 6, 2) : -Inf : alloca[1,2] + alloca[6,2] : 1.0 : True (1, 6, 3) : -Inf : alloca[1,3] + alloca[6,3] : 1.0 : True (2, 8, 0) : -Inf : alloca[2,0] + alloca[8,0] : 1.0 : True (2, 8, 1) : -Inf : alloca[2,1] + alloca[8,1] : 1.0 : True (2, 8, 2) : -Inf : alloca[2,2] + alloca[8,2] : 1.0 : True (2, 8, 3) : -Inf : alloca[2,3] + alloca[8,3] : 1.0 : True (2, 9, 0) : -Inf : alloca[2,0] + alloca[9,0] : 1.0 : True (2, 9, 1) : -Inf : alloca[2,1] + alloca[9,1] : 1.0 : True (2, 9, 2) : -Inf : alloca[2,2] + alloca[9,2] : 1.0 : True (2, 9, 3) : -Inf : alloca[2,3] + alloca[9,3] : 1.0 : True (3, 4, 0) : -Inf : alloca[3,0] + alloca[4,0] : 1.0 : True (3, 4, 1) : -Inf : alloca[3,1] + alloca[4,1] : 1.0 : True (3, 4, 2) : -Inf : alloca[3,2] + alloca[4,2] : 1.0 : True (3, 4, 3) : -Inf : alloca[3,3] + alloca[4,3] : 1.0 : True (3, 5, 0) : -Inf : alloca[3,0] + alloca[5,0] : 1.0 : True (3, 5, 1) : -Inf : alloca[3,1] + alloca[5,1] : 1.0 : True (3, 5, 2) : -Inf : alloca[3,2] + alloca[5,2] : 1.0 : True (3, 5, 3) : -Inf : alloca[3,3] + alloca[5,3] : 1.0 : True (4, 5, 0) : -Inf : alloca[4,0] + alloca[5,0] : 1.0 : True (4, 5, 1) : -Inf : alloca[4,1] + alloca[5,1] : 1.0 : True (4, 5, 2) : -Inf : alloca[4,2] + alloca[5,2] : 1.0 : True (4, 5, 3) : -Inf : alloca[4,3] + alloca[5,3] : 1.0 : True (7, 8, 0) : -Inf : alloca[7,0] + alloca[8,0] : 1.0 : True (7, 8, 1) : -Inf : alloca[7,1] + alloca[8,1] : 1.0 : True (7, 8, 2) : -Inf : alloca[7,2] + alloca[8,2] : 1.0 : True (7, 8, 3) : -Inf : alloca[7,3] + alloca[8,3] : 1.0 : True 10 Declarations: phys_regs phys_costs virt_regs alloca_index alloca bad_pairs obj виртуальному_один_физический использование_одного_физического_index использование_одного_физического
solver = pyo.SolverFactory('cbc') solver.solve(m).write() for v in m.component_data_objects(pyo.Var): if v.value and v.value > 0: print(str(v), v.value)
# ========================================================== # = Solver Results = # ========================================================== # ---------------------------------------------------------- # Problem Information # ---------------------------------------------------------- Problem: - Name: unknown Lower bound: 18.0 Upper bound: 18.0 Number of objectives: 1 Number of constraints: 62 Number of variables: 40 Number of binary variables: 40 Number of integer variables: 40 Number of nonzeros: 40 Sense: minimize # ---------------------------------------------------------- # Solver Information # ---------------------------------------------------------- Solver: - Status: ok User time: -1.0 System time: 0.01 Wallclock time: 0.02 Termination condition: optimal Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available. Statistics: Branch and bound: Number of bounded subproblems: 0 Number of created subproblems: 0 Black box: Number of iterations: 0 Error rc: 0 Time: 0.06682181358337402 # ---------------------------------------------------------- # Solution Information # ---------------------------------------------------------- Solution: - number of solutions: 0 number of solutions displayed: 0 alloca[0,0] 1.0 alloca[1,3] 1.0 alloca[2,0] 1.0 alloca[3,1] 1.0 alloca[4,2] 1.0 alloca[5,0] 1.0 alloca[6,0] 1.0 alloca[7,0] 1.0 alloca[8,1] 1.0 alloca[9,1] 1.0

Визуализируем используемые регистры инструкций после аллокации (заменим виртуальные регистры на физические)

phys_uses = [] for use in virtual_uses: phys_uses.append([f"{p:02}" for v in use for p in range(phys_regs_amount) if pyo.value(m.alloca[int(v), p])]) svg = psc.subsets2svg(phys_uses) SVG(data=svg)
Image in a Jupyter notebook